Estimating advertisability of tail queries for sponsored search.

Efficiently evaluating complex boolean expressions.

Using landing pages for sponsored search ad selection.

A search%2Dbased method for forecasting ad impression in contextual advertising.
Contextual advertising (also called content match) refers to the placement of small textual ads within the content of a generic web page. It has become a significant source of revenue for publishers ranging from individual bloggers to major newspapers. At the same time it is an important way for advertisers to reach their intended audience. This reach depends on the total number of exposures of the ad (impressions) and its click-through-rate (CTR) that can be viewed as the probability of an end-user clicking on the ad when shown. These two orthogonal, critical factors are both difficult to estimate and even individually can still be very informative and useful in planning and budgeting advertising campaigns. In this paper, we address the problem of forecasting the number of impressions for new or changed ads in the system.
Classifying search queries using the Web as a source of knowledge.
We propose a methodology for building a robust query classification system that can identify thousands of query classes, while dealing in real-time with the query volume of a commercial Web search engine. We use a pseudo relevance feedback technique: given a query, we determine its topic by classifying the Web search results retrieved by the query. Motivated by the needs of search advertising, we primarily focus on rare queries, which are the hardest from the point of view of machine learning, yet in aggregation account for a considerable fraction of search engine traffic. Empirical evaluation confirms that our methodology yields a considerably higher classification accuracy than previously reported. We believe that the proposed methodology will lead to better matching of online ads to rare queries and overall to a better user experience.
To swing or not to swing learning when %28not%29 to advertise.
Web textual advertising can be interpreted as a search problem over the corpus of ads available for display in a particular context. In contrast to conventional information retrieval systems, which always return results if the corpus contains any documents lexically related to the query, in Web advertising it is acceptable, and occasionally even desirable, not to show any results. When no ads are relevant to the user’s interests, then showing irrelevant ads should be avoided since they annoy the user and produce no economic benefit. In this paper we pose a decision problem “whether to swing”, that is, whether or not to show any of the ads for the incoming request. We propose two methods for addressing this problem, a simple thresholding approach and a machine learning approach, which collectively analyzes the set of candidate ads augmented with external knowledge. Our experimental evaluation, based on over 28,000 editorial judgments, shows that we are able to predict, with high accuracy, when to“swing”for both content match and sponsored search advertising.
Search advertising using web relevance feedback.

A note on search based forecasting of ad volume in contextual advertising.
In contextual advertising, estimating the number of impressions of an ad is critical in planning and budgeting advertising campaigns. However, producing this forecast, even within large margins of error, is quite challenging. We attack this problem by simulating the presence of a given ad with its associated bid over historical data, involving billions of impressions. This apparently enormous computational task is reduced to a search task involving only the set of distinct pages in the data. Furthermore the search is made more efficient using a two-level search process. Experimental results show that our approach can accurately forecast the expected number of impressions of contextual ads in real time.
Relaxation in text search using taxonomies.
In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result quality. This new model may be applicable in many arenas, including multifaceted, product, and local search, where documents are augmented with hierarchical metadata such as topic or location. We present efficient algorithms for indexing and query processing in this new retrieval model. We decompose query processing into two sub-problems: first, an online search problem to determine the correct overall level of relaxation cost that must be incurred to generate the top k results; and second, a budgeted relaxation search problem in which all results at a particular relaxation cost must be produced at minimal cost. We show the latter problem is solvable exactly in two hierarchical dimensions, is NP-hard in three or more dimensions, but admits efficient approximation algorithms with provable guarantees. We present experimental results evaluating our algorithms on both synthetic and real data, showing order of magnitude improvements over the baseline algorithm. 1.
Robust classification of rare queries using web knowledge.

Robust classification of rare queries using web knowledge.

A semantic approach to contextual advertising.

Inverted Index Support for Numeric Search.
Today’s search engines are increasingly required to broaden their capabilities beyond free-text search. More complex features, such as supporting range constraints over numeric data, are becoming common; structured search over XML data will soon follow. This is particularly true in the enterprise search domain, where engines attempt to integrate data from the Web and corporate knowledge portals with data residing in proprietary databases. In this paper we extend previous schemes by which an inverted index based search engine can efficiently support queries that contain numeric restrictions in addition to standard, free-text portions. Furthermore, we analyze both the known schemes and our extensions in terms of index-build time, index space and query processing time. We show how to maximize query processing performance while respecting limits on index size and build time, or conversely, how to minimize index space and build time while maintaining guarantees on runtime performance. Thus, we concisely analyze the trade-off between index size and build time, and runtime performance. Finally, we present experimental results that demonstrate significant performance benefits attained by our method, as compared to alternative approaches. 1
On the memory requirements of XPath evaluation over XML streams.
The important challenge of evaluating XPath queries over XML streams has sparked much interest in the past few years. A number of algorithms have been proposed, supporting wider fragments of the query language, and exhibiting better performance and memory utilization. Nevertheless, all the algorithms known to date use a prohibitively large amount of memory for certain types of queries. A natural question then is whether this memory bottleneck is inherent or just an artifact of the proposed algorithms. In this paper we initiate the first systematic and theoretical study of lower bounds on the amount of memory required to evaluate XPath queries over XML streams. We present a general lower bound technique, which given a query, specifies the minimum amount of memory that any algorithm evaluating the query on a stream would need to incur. The lower bounds are stated in terms of new graph-theoretic properties of queries. The proofs are based on tools from communication complexity. We then exploit insights learned from the lower bounds to obtain a new algorithm for XPath evaluation on streams. The algorithm uses space close to the optimum. Our algorithm deviates from the standard paradigm of using automata or transducers, thereby avoiding the need to store large transition tables. 1
Estimating corpus size via queries.

Indexing Shared Content in Information Retrieval Systems.
Abstract. Modern document collections often contain groups of documents with overlapping or shared content. However, most information retrieval systems process each document separately, causing shared content to be indexed multiple times. In this paper, we describe a new document representation model where related documents are organized as a tree, allowing shared content to be indexed just once. We show how this representation model can be encoded in an inverted index and we describe algorithms for evaluating free-text queries based on this encoding. We also show how our representation model applies to web, email, and newsgroup search. Finally, we present experimental results showing that our methods can provide a significant reduction in the size of an inverted index as well as in the time to build and query it. 1
Using annotations in enterprise search.

A Rule%2DBased Approach to Framework Evolution.

Framework Evolution Tool.
The activities of configuration management and version control are common to a  number of engineering tasks. These activities are particularly important for  software engineers since they, during most of a system life cycle, have to deal  with a growing number of versions of a single component, and to rebuild the  complete system in different ways using different components.  These tasks are repetitive and trivial, and require a lot of manual work and  accuracy. In this paper we show how the problem of automate these activities has  been solved in a number of software development environments. We describe the  evolution of systems for configuration management and version control from  simple stand alone tools such as make and SCCS, based on an underlying file  system, towards more integrated systems based on a project database.  1  V.Ambriola is with Dipartimento di Matematica e Informatica, Universit di Udine.  2  This work has been partially supported by Ministero della Pubblica Istr...
Static score bucketing in inverted indexes.

Optimizing cursor movement in holistic twig joins.

Buffering in query evaluation over XML streams.

Decentralized Peer%2Dto%2DPeer Auctions.
This paper proposes a flexible architecture for the creation of Internet auctions. It allows the custom definition of the auction parameters, and provides a decentralized control of the auction process. Auction policies are defined as laws in the Law Governed Interaction (LGI) paradigm. Each of these laws specifies not only the auction algorithm itself (e.g. open-cry, dutch, etc.) but also how to handle the other parameters usually involved in the online auctions, such as certification, auditioning, and treatment of complaints. LGI is used to enforce the rules established in the auction policy within the agents involved in the process. After the agents find out about the actions, they interact in a peer-to-peer communication protocol, reducing the role of the centralized auction room to an advertising registry, and taking profit of the distributed nature of the Internet to conduct the auction. The paper presents an example of an auction law, illustrating the use of the proposed architecture. 1
Querying XML streams.
Streaming algorithms for Xml query answering call for efficient memory management. Tractable queries are distinguished by a bounded number of concurrently alive answer candidates at every time point, and a bounded delay for node selection, for every candidate. We show that both properties are decidable in polynomial time for queries defined by deterministic tree automata. Our results are obtained by reduction to the bounded valuedness problem for recognizable relations between unranked trees, a problem that we show to be decidable in polynomial time. Key words: streaming, tree automata, Xml, databases. 1.
Virtual cursors for XML joins.

On the Memory Requirements of XPath Evaluation over XML Streams.
The important challenge of evaluating XPath queries over XML streams has sparked much interest in the past few years. A number of algorithms have been proposed, supporting wider fragments of the query language, and exhibiting better performance and memory utilization. Nevertheless, all the algorithms known to date use a prohibitively large amount of memory for certain types of queries. A natural question then is whether this memory bottleneck is inherent or just an artifact of the proposed algorithms. In this paper we initiate the first systematic and theoretical study of lower bounds on the amount of memory required to evaluate XPath queries over XML streams. We present a general lower bound technique, which given a query, specifies the minimum amount of memory that any algorithm evaluating the query on a stream would need to incur. The lower bounds are stated in terms of new graph-theoretic properties of queries. The proofs are based on tools from communication complexity. We then exploit insights learned from the lower bounds to obtain a new algorithm for XPath evaluation on streams. The algorithm uses space close to the optimum. Our algorithm deviates from the standard paradigm of using automata or transducers, thereby avoiding the need to store large transition tables. 1
High Performance Index Build Algorithms for Intranet Search Engines.

Guest editorial Ubiquitous computing.

Streaming XPath Processing with Forward and Backward Axes.
We present a streaming algorithm for evaluating XPath expressions that use backward axes (parent and ancestor) and forward axes in a single document-order traversal of an XML document. Other streaming XPath processors handle only forward axes. We show through experiments that our algorithm significantly outperforms (by more than a factor of two) a traditional non-streaming XPath engine. Furthermore, our algorithm scales better because it retains only the relevant portions of the input document in memory. Our engine successfully processes documents over 1GB in size, whereas the traditional XPath engine degrades considerably in performance for documents over 100 MB in size and fails to complete for documents of size over 200 MB. 1
TSpaces Services Suite Automating the Development and Management of Web Services.
Web services allow authorized entities (including individuals, corporations, and automated agents) to employ software components created by other parties scattered across the globe. In support of this powerful model of interaction, we have designed and implemented an infrastructure and a set of tools to simplify the development and management of Web services. This infrastructure and these tools form the TSpaces Services Suite (TSSuite). This paper shows how TSSuite supports the Web services model, and it describes the design and functionality of the main TSSuite components. Categories and Subject Descriptors D.2.3 [Software Engineering]: Design Tools and Techniques –
Using refactoring and unification rules to assist framework evolution.

Product Line Annotations with UML%2DF.
The Unified Modeling Language (UML) community has started to  define so-called profiles in order to better suit the needs of specific domains or  settings. Product lines    represent a special breed of systems---they are extensible  semi-finished pieces of software. Completing the semi-finished software  leads to various software pieces, typically specific applications, which share the  same core. Though product lines have been developed for a wide range of domains,  they apply common construction principles. The intention of the UML-F  profile is the definition of a UML subset, enriched with a few UML-compliant  extensions, which allows the annotation of such artifacts. The paper presents  aspects of the profile with a focus on patterns and exemplifies its usage.
Law%2Dgoverned peer%2Dto%2Dpeer auctions.
This paper proposes a flexible architecture for the creation of Internet auctions. It allows the custom definition of the auction parameters, and provides a decentralized control of the auction process. Auction policies are defined as laws in the Law Governed Interaction (LGI) paradigm. Each of these laws specifies not only the auction algorithm itself (e.g. open-cry, dutch, etc.) but also how to handle the other parameters usually involved in the online auctions, such as certification, auditioning, and treatment of complaints. LGI is used to enforce the rules established in the auction policy within the agents involved in the process. After the agents find out about the actions, they interact in a peer-to-peer communication protocol, reducing the role of the centralized auction room to an advertising registry, and taking profit of the distributed nature of the Internet to conduct the auction. The paper presents an example of an auction law, illustrating the use of the proposed architecture.
Editors%27 Introduction.
This paper reports on solving instances with more than 10,000 data items in a few hours. Keane, Page, Naughton, Travers and McInerney report on a fully cross platform coarse-grained distributed application for building large phylogenetic trees. Their new system overcomes many of the limitations imposed by the current set of parallel phylogenetic programs and it is now publicly available. The next two papers deal with gene and protein sequence comparison. Alves, Caceres and Song present a new coarse-grained parallel algorithm for the all-substrings longest common subsequence operation which is used, e.g. to find approximate tandem repeats and the alignment of one sequence with several others that have a common subsequence. Driga, Lu, Schaeffer, Szafron, Charter and Parsons discuss parallel and sequential sequence alignment via a method called FastLSA. Experiments indicate that their method scales well and can be parameterized to take advantage of cache memory and main memory sizes
Introduction special issue on chains of commitment.

Using UML%2DF to enhance framework development a case study in the local search heuristics domain.
Currently frameworks are most commonly represented through design diagrams written in standard objectoriented analysis and design languages. However, these design notations do not provide elements for identifying framework variation points and how their instantiation should be performed. Therefore, in order to create framework instances, users have to rely on extra documentation that is not always available. This paper shows the benefits of an extension to UML that explicitly represents all the information required for framework development and instantiation. The approach is illustrated through a large real-world framework for local search heuristics for combinatorial optimization problems.  KEY WORDS: object-oriented frameworks, design notation, UML-F, framework development, framework instantiation.  1. INTRODUCTION  This paper illustrates the weakness of standard object-oriented design languages regarding framework documentation and shows how UML-F (Fontoura, 1999; Fontoura et. al., ...
The WebShop E%2DCommerce Framework.
Abstract- This paper presents an e-commerce framework called WebShop, which was developed by the authors for the purpose of demonstrating the use of UML and the UML-F in the domain of Web applications. Thus, the WebShop is not regarded as a full-fledged system out of which real Web stores can be derived. For example, the framework in the presented version does not encounter security features. However, it presents the most important variation points related to online catalogs. The UML-F Web site
Using UML%2DF to enhance framework development a case study in the local search heuristics domain.
Currently frameworks are most commonly represented through design diagrams written in standard objectoriented analysis and design languages. However, these design notations do not provide elements for identifying framework variation points and how their instantiation should be performed. Therefore, in order to create framework instances, users have to rely on extra documentation that is not always available. This paper shows the benefits of an extension to UML that explicitly represents all the information required for framework development and instantiation. The approach is illustrated through a large real-world framework for local search heuristics for combinatorial optimization problems.  KEY WORDS: object-oriented frameworks, design notation, UML-F, framework development, framework instantiation.  1. INTRODUCTION  This paper illustrates the weakness of standard object-oriented design languages regarding framework documentation and shows how UML-F (Fontoura, 1999; Fontoura et. al., ...
UML%2DF A Modeling Language for Object%2DOriented Frameworks.
Abstract. The paper presents the essential features of a new member of the UML language family that supports working with object-oriented frameworks. This UML extension, called UML-F, allows the explicit representation of framework variation points. The paper discusses some of the relevant aspects of UML-F, which is based on standard UML extension mechanisms. A case study shows how it can be used to assist framework development. A discussion of additional tools for automating framework implementation and instantiation rounds out the paper. 1
Framework Development and Adaptation with UML.

Using viewpoints to derive object%2Doriented frameworks a case study in the web%2Dbased education domain.

V%2DMarket A framework for agent e%2Dcommerce systems.
Software agent technology is still an emerging technology, and as such, agent based software design is still in its infancy. Software agents have just started to be used in the e-commerce domain, and they are already beginning to create a series of new possibilities for this arena. Agents can be used to automate, as well as to enhance many stages of the traditional consumer-buying behavior process. This paper proposes a software engineering approach to the design of agent mediated e-commerce systems, through the definition of an object-oriented framework. The paper presents the underlying concepts, and the architecture of the environment, showing how it allows developers to customize virtual marketplaces, and to define transaction categories on demand, incorporating many possible products and services that can be traded online. 
Um Ambiente para Modelagem e Execu%E7%E3o de Processos.

